package cn.jdemo.algorithm.sort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;

/**
 * 快速排序
 *  (1) 基准数，游标
 *  (2) 基于基准数，小于基准数的放到基准数的位置，大于基准数的右移；
 *
 * @date 2020/12/25
 */
public class Demo01_QuickSort {
    private static final Logger logger = LoggerFactory.getLogger(Demo01_QuickSort.class);

    public static void main(String[] args) {
        int[] arrs = new int[]{6,5,4,9,10,3,1,2,0};
        quickSort(arrs,0,arrs.length-1);
        for (int i = 0; i < arrs.length; i++) {
            System.out.print(arrs[i]+" ");
        }
    }

    public static void quickSort(int[] nums, int left, int right){
        if(left >= right){
            return;
        }
        int p = partition(nums,left,right);
        quickSort(nums,left,p-1);
        quickSort(nums,p+1,right);
    }


    private static int partition(int[] arr, int l, int r) {
        int pivot = arr[l]; // 基准
        int index = l + 1;
        for (int i = index; i <= r; i++) {
            if (arr[i] < pivot) {
                swap(arr, i, index); // 交换后的 arr[j] 为当前最后一个小于基准的元素
                index++;
            }
        }
        swap(arr, l, index - 1);
        return index - 1;// 基准最终下标
    }

    public static void swap(int[] arr, int i,int j){
        if(i == j){
            return; // 不用交换，下述方式不支持i与j相同时交换
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

}
